import static org.junit.Assert.*;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

import org.junit.Test;


public class Tests {

	@Test
	public void testSearch() { // edges pointing in both directions
		//aaa();
		//aaapairlist();
		Map<String, List<String>> adjList = new HashMap <String, List<String>>();
		adjList.put("A", (toliststr("B,C,D")));/// no spaces in "A" or "B,C,D" !
		adjList.put("B", (toliststr("A,G,E")));
		adjList.put("C", (toliststr("A,D,E")));
		adjList.put("D", (toliststr("C")));
		adjList.put("E", (toliststr("B,C,F")));
		adjList.put("F", (toliststr("E")));
		adjList.put("G", (toliststr("B")));
		
		
		StructureStack<String> ss = new StructureStack<String>();
		StructureQueue<String> sq = new StructureQueue<String>();
		
		assertTrue(GraphSearch.search("A", ss, adjList, "E"));
		assertTrue(GraphSearch.search("A", sq, adjList, "E"));
		
		assertTrue(GraphSearch.search("A", ss, adjList, "F"));
		assertTrue(GraphSearch.search("A", sq, adjList, "F"));
		
		assertFalse(GraphSearch.search("A", ss, adjList, "M"));
		assertFalse(GraphSearch.search("A", sq, adjList, "M"));
		
		assertTrue(GraphSearch.search("G", ss, adjList, "F"));
		assertTrue(GraphSearch.search("G", sq, adjList, "F"));
		
		assertTrue(GraphSearch.search("G", ss, adjList, "B"));
		assertTrue(GraphSearch.search("G", sq, adjList, "B"));
		
		assertTrue(GraphSearch.search("B", ss, adjList, "F"));
		assertTrue(GraphSearch.search("B", sq, adjList, "F"));
		
		assertTrue(GraphSearch.search("G", ss, adjList, "D"));
		assertTrue(GraphSearch.search("G", sq, adjList, "D"));
		
		assertFalse(GraphSearch.search("B", ss, adjList, "K"));
		assertFalse(GraphSearch.search("B", sq, adjList, "K"));
	}
	@Test
	public void testSearch2() { // edges pointing in only one direction
	
		Map<String, List<String>> adjList = samplesearch();
		
		StructureStack<String> ss = new StructureStack<String>();
		StructureQueue<String> sq = new StructureQueue<String>();
		
		assertTrue(GraphSearch.search("A", ss, adjList, "E"));
		assertTrue(GraphSearch.search("A", sq, adjList, "E"));
		
		assertTrue(GraphSearch.search("A", ss, adjList, "F"));
		assertTrue(GraphSearch.search("A", sq, adjList, "F"));
		
		assertFalse(GraphSearch.search("A", ss, adjList, "M"));
		assertFalse(GraphSearch.search("A", sq, adjList, "M"));
		
		assertFalse(GraphSearch.search("G", ss, adjList, "F"));
		assertFalse(GraphSearch.search("G", sq, adjList, "F"));
		
		assertFalse(GraphSearch.search("G", ss, adjList, "B"));
		assertFalse(GraphSearch.search("G", sq, adjList, "B"));
		
		assertTrue(GraphSearch.search("B", ss, adjList, "F"));
		assertTrue(GraphSearch.search("B", sq, adjList, "F"));
	}

	@Test
	public void testSearch3_complicated() { // edges pointing in only one direction
		//aaa();
		//aaapairlist();
		Map<String, List<String>> adjList = new HashMap <String, List<String>>();
		adjList.put("A", (toliststr("B,C")));
		adjList.put("B", (toliststr("E")));
		adjList.put("C", (toliststr("D")));
		adjList.put("D", (toliststr("A")));
		adjList.put("E", (toliststr("C,F")));
		adjList.put("F", (toliststr("")));
		adjList.put("G", (toliststr("B")));
		
		
		StructureStack<String> ss = new StructureStack<String>();
		StructureQueue<String> sq = new StructureQueue<String>();
		
		assertTrue(GraphSearch.search("A", ss, adjList, "E"));
		assertTrue(GraphSearch.search("A", sq, adjList, "E"));
		
		assertTrue(GraphSearch.search("A", ss, adjList, "F"));
		assertTrue(GraphSearch.search("A", sq, adjList, "F"));
		
		assertTrue(GraphSearch.search("G", ss, adjList, "F"));
		assertTrue(GraphSearch.search("G", sq, adjList, "F"));
		
		assertTrue(GraphSearch.search("G", ss, adjList, "C"));
		assertTrue(GraphSearch.search("G", sq, adjList, "C"));
		
		assertTrue(GraphSearch.search("G", ss, adjList, "A"));
		assertTrue(GraphSearch.search("G", sq, adjList, "A"));
		
		assertTrue(GraphSearch.search("G", ss, adjList, "D"));
		assertTrue(GraphSearch.search("G", sq, adjList, "D"));
		
		assertTrue(GraphSearch.search("E", ss, adjList, "A"));
		assertTrue(GraphSearch.search("E", sq, adjList, "A"));
		
		assertTrue(GraphSearch.search("D", ss, adjList, "F"));
		assertTrue(GraphSearch.search("D", sq, adjList, "F"));
		
		assertTrue(GraphSearch.search("D", ss, adjList, "C"));
		assertTrue(GraphSearch.search("D", sq, adjList, "C"));
		
		assertFalse(GraphSearch.search("A", ss, adjList, "M"));
		assertFalse(GraphSearch.search("A", sq, adjList, "M"));
		
		assertFalse(GraphSearch.search("A", ss, adjList, "G"));
		assertFalse(GraphSearch.search("A", sq, adjList, "G"));
		
		assertFalse(GraphSearch.search("C", ss, adjList, "G"));
		assertFalse(GraphSearch.search("C", sq, adjList, "G"));
		
		assertFalse(GraphSearch.search("F", ss, adjList, "B"));
		assertFalse(GraphSearch.search("F", sq, adjList, "B"));
		
		assertFalse(GraphSearch.search("F", ss, adjList, "M"));
		assertFalse(GraphSearch.search("F", sq, adjList, "M"));
	}
	@Test
	public void testDsp() { // edges pointing in both directions
		//aaapairlist();
		Map<String, List<Pair<String, Integer>>> adjList = sampledsp();
		assertEquals(11, GraphSearch.dsp("A", adjList, "B"));
		assertEquals(8, GraphSearch.dsp("A", adjList, "C"));
		assertEquals(32, GraphSearch.dsp("A", adjList, "D"));
		assertEquals(55, GraphSearch.dsp("A", adjList, "E"));
		assertEquals(35, GraphSearch.dsp("A", adjList, "F"));
		
	}
	
	@Test
	public void testDsp2() {//// edges pointing in only one direction
		//aaapairlist();
		Map<String, List<Pair<String, Integer>>> adjList = new HashMap<String, List<Pair<String, Integer>>>();
		adjList.put("A", tolistpair("B,1:C,5"));// make sure no spaces in any of those strings!
		adjList.put("B", tolistpair("E,2"));
		adjList.put("C", tolistpair("D,5"));
		adjList.put("D", tolistpair("A,2"));
		adjList.put("E", tolistpair("C,5:F,1"));
		adjList.put("F", tolistpair("F,0"));// just put the node itself and distance as 0 if that node is not pointing to any other node
		adjList.put("G", tolistpair("B,4"));
		
		
		assertEquals(0, GraphSearch.dsp("A", adjList, "A"));
		assertEquals(1, GraphSearch.dsp("A", adjList, "B"));
		assertEquals(4, GraphSearch.dsp("A", adjList, "F"));
		assertEquals(-1, GraphSearch.dsp("A", adjList, "G"));
		assertEquals(10, GraphSearch.dsp("A", adjList, "D"));
		assertEquals(2, GraphSearch.dsp("D", adjList, "A"));
		assertEquals(7, GraphSearch.dsp("D", adjList, "C"));
		assertEquals(18, GraphSearch.dsp("G", adjList, "A"));
		assertEquals(16, GraphSearch.dsp("G", adjList, "D"));
		assertEquals(10, GraphSearch.dsp("C", adjList, "E"));
		assertEquals(-1, GraphSearch.dsp("F", adjList, "A"));
		assertEquals(-1, GraphSearch.dsp("F", adjList, "O"));
		assertEquals(-1, GraphSearch.dsp("E", adjList, "O"));
		assertEquals(-1, GraphSearch.dsp("A", adjList, "O"));
		assertEquals(-1, GraphSearch.dsp("B", adjList, "O"));
		
	}
	
	
	private  Map<String, List<String>> samplesearch(){
		Map<String, List<String>> s = new HashMap<String , List<String>> ();
		s.put("A", (toliststr("B,C,G")));// make sure no spaces in that string! 
		s.put("B", toliststr("E"));// make sure no spaces in that string! 
		s.put("C", toliststr("E,D"));
		s.put("D", toliststr(""));
		s.put("E", toliststr("F"));
		s.put("F", toliststr(""));
		s.put("G", toliststr(""));
		return s;
	}
	private Map<String, List<Pair<String, Integer>>> sampledsp(){
		Map<String, List<Pair<String, Integer>>> dsp = new HashMap<String, List<Pair<String, Integer>>>();
		dsp.put("A", tolistpair("B,12:C,8:D,43:E,79:F,35"));// make sure no spaces in any of those strings! 
		dsp.put("B", tolistpair("A,93:C,18:D,21:E,60:F,33"));// make sure no spaces in that string! 
		dsp.put("C", tolistpair("A,17:B,3:D,37:E,50:F,30"));
		dsp.put("D", tolistpair("A,85:B,10:C,91:E,17:F,7"));
		dsp.put("E", tolistpair("A,28:B,47:C,39:D,14:F,108"));
		dsp.put("F", tolistpair("A,31:B,7:C,29:D,73:E,20"));
		
		return dsp;
	}
	
	private List<Pair<String, Integer>> tolistpair(String str){
		List <Pair<String, Integer>> list1 = new ArrayList <Pair<String, Integer>> () ;
		if (str == ""){
			list1.add(new Pair<String, Integer>("",0));
		}
		else{
			String []arr1 = str.split(":");
			for (String s : arr1){
				String [] strmini = s.split(",");
				//String strmini1 = strmini[0];
				//Integer strmini2 = new Integer(strmini[1]);
				System.out.println("Childs are "+ strmini[0] +" Didt of  " + new Integer(strmini[1]));
				list1.add(new Pair<String, Integer>(strmini[0], new Integer(strmini[1])));
			}
		}
		return list1;
	}

	private  List<String> toliststr(String string){
		String[] arr1 =  string.split(",");
		//System.out.println(Arrays.toString(arr1));
		//System.out.println(arr1.length);
		List <String> list1 = Arrays.asList(arr1);
		//System.out.println(Arrays.toString(list1.toArray()));
	
		return list1;
	}
	
	public void aaa(){
		Map<String, List<String>> a = samplesearch();
		List<String> l = a.get("A");
		for (String s: l){
			System.out.println("A's neb : " + s);
		}
		List<String> l2 = a.get("B");
		for (String s: l2){
			System.out.println("B's neb : " + s);
		}
	}
	public void aaapairlist(){
		Map<String, List<Pair<String, Integer>>> a = sampledsp();
		List <Pair<String, Integer>> l = a.get("A");
		for (Pair<String, Integer> s: l){
			System.out.println("A's neb : " + s.a + " and dist of : " +s.b);
		}
		List <Pair<String, Integer>> l2 = a.get("G");
		for (Pair<String, Integer> s: l2){
			System.out.println("G's neb : " + s.a + " and dist of : " +s.b);
		}
	}
}
